Digital signal processing (DSP) is broadly defined as any digital operation performed on an input sequence of numbers. The sequence of numbers can represent a wide range of data, from simple data such as daily temperatures to complex data such as digitized samples of a human voice. DSP can be used for a variety of purposes, such as, for example, digital filtering, determining the presence of a periodic signal, determining the periodic frequency content of a signal, generating sinusoidal waveforms, and replacing analog circuitry with a DSP software equivalent.
A very useful and common mathematical operation in DSP systems is the "multiply and accumulate" or "MAC" operation. For example, digital filtering can be accomplished with multiply and accumulate operations using current and past digital values of the data multiplied by filter coefficients. The values of the filter coefficients determine the characteristics of the filter, such as lowpass, highpass, bandpass, etc. As each digital value is multiplied by the corresponding filter coefficient, the resulting product is added to the sum of all of the prior products. Although the multiply and accumulate operation is relatively simple, the number of MAC operations required to perform a useful DSP function, such as digital filtering, is potentially very large. Thus, methods which reduce the time and software overhead required to perform basic DSP operations are very important.
Circular buffers or queues are often used to implement a digital filter. While one queue holds the digital values of periodic samples of the signal to be filtered, another queue holds the values of the filter coefficients. Modulo arithmetic os commonly used to perform address calculations for circular buffers. The address calculations are performed on integer values, and the resulting address is used to access data contained in a data storage device. Data storage devices are typically implemented by conventional memory circuits having linear addressing capability.
Linear arithmetic is an arithmetic form commonly found in data processors and is typically implemented by conventional two's complement binary arithmetic. However, there is a considerable amount of software overhead associated with using linear arithmetic to implement memory data structures such as circular buffers, queues, or FIFOs. This extra overhead is due to the fact that linear arithmetic has no ability to directly perform a "wraparound" operation to maintain an address within a defined range. Modulo arithmetic, on the other hand, directly performs a wraparound function with no overhead. Thus, modulo arithmetic allows data structures such as circular buffers, queues, and FIFOs to be implemented with less overhead than is required by linear arithmetic.
In an abstract mathematical sense, "modulo M" arithmetic uses a number system to the base M where each digit of the number system is represented by a predetermined value within a range from 0 thru (M-1), where M is an integer. A representation of "(N)modulo M" is essentially equal to the "remainder" of N to the base M. For example, the representation (12)modulo 10 is equal to 2. As calculations of (R.+-.N)modulo M are preformed on numbers R and N, which each are within a range from 0 thru (M-1), the resultant must also be a number within the defined range. If a lower boundary value, L, of the range is not equal to zero, a modulo value resulting from an arithmetic calculation is no longer literally equal to a remainder value. The resultant is offset from 0 by the value of the lower boundary L and the modulo arithmetic calculation becomes equal to: EQU [(R.+-.N-L)modulo M]+L.
Existing modulo addressing schemes, although very flexible, require a significant amount of hardware. As the demand for higher performance microcontrollers (MCUs) increases, semiconductor manufacturers are looking for ways to design MCUs with as much functionality as possible within the confines of a small amount of circuitry and silicon area. MCUs have developed to the point where it is desirable for them to have the ability to perform basic DSP functions. The primary trade-off in designing circuitry to perform DSP functions is the trade-off between silicon area on the one hand, and speed and flexibility on the other hand. Generally, the more steps of a DSP algorithm that are implemented in hardware rather than software, the faster the DSP algorithm can be performed, but the more silicon area that must be used. Also, the more flexibility that the user is provided in terms of parameters that can be user programmed for the DSP algorithm, the more silicon area that is required.
The present invention does not have as much flexibility as most dedicated DSP processors because the present invention reflects this trade-off between silicon area on the one hand, and speed and flexibility on the other hand. The present invention only allows modulo base values (M) equal to 2 to the power X, where X is an integer; whereas, most dedicated DSP processors allow the user to program a wider range of modulo values. However, this invention requires very little dedicated silicon area in an MCU. The present invention gives the user a limited, but very useful ability to do DSP processing with a minimal cost in terms of silicon area.